<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            1. dp数组含义：代表经过的可能的步骤
            2. 递推公式：dp[i, j] = dp[i - 1, j] + dp[i, j - 1]
            3. 初始化dp数组：dp[0, 1] = 1; dp[1, 0] = 1
            4. 递推的顺序：值由上方和左方的值推导而来
            5. 模拟：(1, 1)的值来自 (1, 0) 和 (0, 1)推导而来
        */

       /* 
          时间和空间都是O(m * n)  
       */
        var uniquePaths = function (m, n) {
            let dp = []
            // 初始化
            for (let i = 0; i < m; i++) {
                dp[i] = []
                for (let j = 0; j < n; j++) {
                    // 第0行和第0列的值都是0
                    if (i === 0 || j === 0) dp[i][j] = 1
                    else dp[i][j] = 0
                }
            }
            for (let i = 0; i < m; i++) {
                for (let j = 0; j < n; j++) {
                    if (i === 0 || j === 0) continue
                    // 递推公式
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
                }
            }
            return dp[m - 1][n - 1]
        };
        console.log(uniquePaths(3, 7));
        // // console.log(uniquePaths(3, 7));
        // console.log(uniquePaths(5, 4)); // 35
    </script>
</body>

</html>